package Sort;
/**
 * 计数排序的场景：
 * 指定范围内的数据
 * 时间复杂度： O(MAX(N,范围))
 * 空间复杂度：O(范围)
 * 稳定性：稳定的排序
 */
public class CountSort {
    public void Sort(int[] array)
    {
        int minVal = array[0];
        int maxVal = array[0];
        for(int a : array)
        {
            if(a > maxVal)
            {
                maxVal = a;
            }
            if (a < minVal)
            {
                minVal = a;
            }
        }
        int len = maxVal - minVal + 1;
        int[] cnt = new int[len];
        for(int i = 0; i < array.length; i++)
        {
            cnt[array[i] - minVal]++;
        }

        int index = 0;
        for(int i = 0; i < cnt.length; i++)
        {
            while (cnt[i] > 0)
            {
                array[index++] = i + minVal;
                cnt[i]--;
            }
        }
    }
}
